#include <cstdio>

struct Matrix
{
    int a[ 4 ][ 4 ], m;
    Matrix( )
    {
        int i, j;
        for ( i = 0; i < 4; i++ )
            for ( j = 0; j < 4; j++ )
                a[ i ][ j ] = 0;
    }
};

Matrix operator * ( const Matrix &a, const Matrix &b )
{
    Matrix c;
    int i, j, k;
    c.m = a.m;
    for ( i = 0; i < 4; i++ )
        for ( j = 0; j < 4; j++ )
        {
            for ( k = 0; k < 4; k++ )
                c.a[ i ][ j ] += a.a[ i ][ k ] * b.a[ k ][ j ];
            c.a[ i ][ j ] %= a.m;
        }
    return c;
}

int main( )
{
    int n, m, i, j, pos;
    Matrix mat, mat_back, f;
    mat_back.a[ 0 ][ 0 ] = mat_back.a[ 0 ][ 1 ] = mat_back.a[ 1 ][ 2 ] = mat_back.a[ 1 ][ 3 ] = mat_back.a[ 2 ][ 0 ] = mat_back.a[ 3 ][ 2 ] = 1;
    while ( scanf("%d%d", &n, &m) != EOF )
    {
        if ( n == 0 )
        {
            puts("0");
            continue;
        }
        if ( n == 1 )
        {
            puts("2");
            continue;
        }
        n -= 2;
        for ( i = 0; i < 4; i++ )
            for ( j = 0; j < 4; j++ )
                f.a[ i ][ j ] = mat.a[ i ][ j ] = 0;
        f.a[ 0 ][ 0 ] = f.a[ 0 ][ 1 ] = f.a[ 0 ][ 2 ] = f.a[ 0 ][ 3 ] = 1;
        mat.a[ 0 ][ 0 ] = mat.a[ 1 ][ 1 ] = mat.a[ 2 ][ 2 ] = mat.a[ 3 ][ 3 ] = 1;
        f.m = mat.m = mat_back.m = m;
        pos = 1;
        while ( pos < n )
            pos <<= 1;
        while ( pos )
        {
            mat = mat * mat;
            if ( pos & n )
                mat = mat * mat_back;
            pos >>= 1;
        }
        f = f * mat;
        printf("%d\n", ( f.a[ 0 ][ 0 ] + f.a[ 0 ][ 1 ] + f.a[ 0 ][ 2 ] + f.a[ 0 ][ 3 ] ) % m);
    }
    return 0;
}
